#include <stack>
using namespace std;
/*
 * @lc app=leetcode.cn id=25 lang=cpp
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
// struct ListNode {
//      int val;
//      ListNode *next;
//      ListNode() : val(0), next(nullptr) {}
//      ListNode(int x) : val(x), next(nullptr) {}
//      ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution {
public:
    // [1, 2]
    // 2 1
    /* 使用栈进行优化
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode node; ListNode *cur = &node;
        cur->next = head; stack<ListNode*> s;
        while (head != nullptr) {
            ListNode *temp = head;
            for (int i = 1; i < k && temp != nullptr; i++) {
                s.push(temp);
                temp = temp->next;
            }
            if (temp == nullptr) break;
            cur->next = temp;
            cur = head; head = temp->next;
            while (!s.empty() && temp != nullptr) {
                temp->next = s.top(); s.pop();
                temp = temp->next; 
            }
            temp->next = head;
        } 
        if (head != nullptr && cur != nullptr) cur->next = head;
        return node.next;
    }
    */
 
   ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode node; ListNode *cur = &node, *m = nullptr;
        cur->next = head; 
        while (head != nullptr) {
            ListNode *temp = head;
            for (int i = 1; i < k && temp != nullptr; i++) {
                temp = temp->next;
            }
            if (temp == nullptr) break;
            m = temp->next;
            auto x = reverseList(head, temp);
            cur->next = x.first; cur = x.second;
            head = m;
        } 
        if (head != nullptr && cur != nullptr) cur->next = head;
        return node.next;
    }

    // 反转链表
    pair<ListNode*, ListNode*> reverseList(ListNode* head, ListNode* tail) {
        ListNode *pre = nullptr, *next = nullptr, *t = head;
        while (pre != tail) {
            next = head->next;
            head->next = pre; pre = head;
            head = next;
        }
        return {pre, t};
    }
};
// @lc code=end

